백준 16236번

아기 상어

Posted by ChoiCube84 on December 26, 2023 · 11 mins read
프로그래밍 문제풀이

백준 16236번

오늘 풀어본 문제는 백준의 16236번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

$N \times N$ 크기의 공간에 물고기 $M$ 마리와 아기 상어 1마리가 있다. 공간은 $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 $1$ 마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 $2$ 이고, 아기 상어는 $1$ 초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.

  • 먹을 수 있는 물고기가 $1$ 마리라면, 그 물고기를 먹으러 간다.

  • 먹을 수 있는 물고기가 $1$ 마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.

    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

    • 아기 상어의 이동은 $1$ 초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 $1$ 증가한다. 예를 들어, 크기가 $2$ 인 아기 상어는 물고기를 $2$ 마리 먹으면 크기가 $3$ 이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 $N$ $(2 \le N \le 20)$ 이 주어진다.

둘째 줄부터 $N$ 개의 줄에 공간의 상태가 주어진다. 공간의 상태는 $0, 1, 2, 3, 4, 5, 6, 9$ 로 이루어져 있고, 아래와 같은 의미를 가진다.

  • $0$: 빈 칸

  • $1, 2, 3, 4, 5, 6$: 칸에 있는 물고기의 크기

  • $9$: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

풀이과정

1번째 시도

문제를 보고 BFS 문제임을 알 수 있었다. 그런데 이런저런 조건이 많아 BFS를 조금 특이하게 활용해야 했다.

문제 조건에 따라 다음에 먹을 물고기를 탐색하되, 이동 거리를 계속해서 누적하는 방식으로 결과를 얻어내야 했고, 이를 find_next 함수를 지속적으로 호출하며 이동 거리의 변화가 없어지는 시점에 결과를 출력하도록 하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

struct SharkStatus {
    pair<int, int> pos;
    int moved = 0;
    int size = 2;
    int eaten = 0;
};

int N;

int grid[20][20] = {0,};

int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};

SharkStatus find_next(SharkStatus start);
bool isInRange(pair<int, int> pos);

int main(void) {
    int result = -1;
    SharkStatus current;

    cin >> N;

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            int temp;
            cin >> temp;

            if (temp == 9) {
                current.pos = {j,i};
                temp = 0;
            }

            grid[j][i] = temp;
        }
    }

    while (true) {
        SharkStatus next = find_next(current);

        if (result == next.moved) {
            break;
        }
        else {
            result = next.moved;
            current = next;
        }
    }

    cout << result;

    return 0;
}

SharkStatus find_next(SharkStatus start) {
    bool visit[20][20] = {false,};

    bool fishFound = false;
    SharkStatus next, bestStatus;
    bestStatus.moved = INT_MAX;

    queue<SharkStatus> q;
    q.push(start);
    visit[start.pos.first][start.pos.second] = true;

    while (!q.empty()) {
        SharkStatus current = q.front();
        q.pop();

        for (int i=0; i<4; i++) {
            int newX = current.pos.first + dx[i];
            int newY = current.pos.second + dy[i];

            if (!visit[newX][newY] && isInRange(make_pair(newX, newY)) && grid[newX][newY] <= current.size) {
                if (grid[newX][newY] == 0 || current.size == grid[newX][newY]) {
                    visit[newX][newY] = true;
                    q.push({make_pair(newX, newY), current.moved + 1, current.size, current.eaten});
                }
                else if (current.size > grid[newX][newY]) {
                    visit[newX][newY] = true;
                    fishFound = true;

                    next.pos = make_pair(newX, newY);
                    next.size = current.size;
                    next.moved = current.moved + 1;
                    next.eaten = current.eaten + 1;

                    if (next.eaten >= next.size) {
                        next.eaten = 0;
                        next.size++;
                    }

                    if (bestStatus.moved > next.moved) {
                        bestStatus = next;
                    }
                    else if (bestStatus.moved == next.moved) {
                        if (bestStatus.pos.second > next.pos.second) {
                            bestStatus = next;
                        }
                        else if (bestStatus.pos.second == next.pos.second) {
                            if (bestStatus.pos.first > next.pos.first) {
                                bestStatus = next;
                            }
                        }
                    }
                }
            }
        }
    }

    if (!fishFound) {
        bestStatus = start;
    }
    else {
        grid[bestStatus.pos.first][bestStatus.pos.second] = 0;
    }

    return bestStatus;
}

bool isInRange(pair<int, int> pos) {
    if (pos.first < 0 || pos.first > N - 1) {
        return false;
    }
    else if (pos.second < 0 || pos.second > N - 1) {
        return false;
    }
    else {
        return true;
    }
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

정말 오랜만에 PS 문제를 다시 풀게 되었다. 9월 16일에 PS 수련을 잠시 중단한 뒤로, 3개월 만이다. 간만에 푸는 문제라 그런지 실력이 꽤 녹슬어 있었다.

이번 방학 계획에 명시적으로 PS 수련을 적어두지는 않았지만, 틈틈히 PS 문제를 풀 것이다. 군대를 가기전에 최소 CLASS 4는 마치고, CLASS 5까지 찍을 수 있었으면 좋겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/16236

← Previous Post Next Post →